package leetcode;

import java.util.*;

/**
 * 下一个更大的元素 1 （栈）
 */
public class NextGreaterElement {
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len = nums1.length;
        int[] res = new int[len];
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        // 让stack1中的元素逐个出栈，直到栈顶为nums1中的元素
        for (int i = 0; i < len; i++) {
            // 先让nums2中所有元素入栈1
            for (int n : nums2) {
                stack1.push(n);
            }
            while (!stack1.isEmpty() && stack1.peek() != nums1[i]) {
                stack2.push(stack1.pop());
            }
            if (!stack1.isEmpty()){
                // 当stack1中栈顶是n,则让stack2中元素逐个出栈并找大值
                while (!stack2.isEmpty()) {
                    int tmp = stack2.peek();
                    if (tmp > nums1[i]) {
                        res[i] = tmp;
                        break;
                    }
                    stack2.pop();
                }
                if (stack2.isEmpty()) {
                    res[i] = -1;
                }
                stack2.clear(); // 最终要将栈2清空
            }
        }
        return res;
    }

    public static int[] nextGreaterElementAnswer1(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] res = new int[m]; // 初始化与nums1等长的结果数组
        for (int i = 0; i < m; ++i) {
            int j = 0;
            while (j < n && nums2[j] != nums1[i]) {
                ++j;
            }
            int k = j + 1;
            while (k < n && nums2[k] < nums2[j]) {
                ++k;
            }
            res[i] = k < n ? nums2[k] : -1;
        }
        return res;
    }

    public static int[] nextGreaterElementAnswer2(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = nums2.length - 1; i >= 0; --i) { // 倒叙存入栈中，则若当前栈顶不大于自己则说明为-1
            int num = nums2[i];
            while (!stack.isEmpty() && num >= stack.peek()) { // 筛选出处于自己后面的值中大于自己的值让其处于栈顶
                stack.pop();
            }
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num); // 将自己入栈，对于下一个元素来说只会看到比当前栈顶还大的（后面更小的被挡住了）
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++i) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }

    public static int[] test(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
//        Deque<Integer> stack = new ArrayDeque<Integer>();
        int[] res = new int[nums1.length];
        for (int i = nums2.length - 1; i >= 0; --i) {
            int num = nums2[i];
            // 找较大值
            while (!stack.isEmpty() && stack.peek() <= num) {
                stack.pop();
            }
            // 后面栈顶元素要么大于num要么栈为空
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }


    public static void main(String[] args) {
        // [4,1,2]
        // [1,3,4,2]
        int[] nums1 = new int[]{4, 1, 2};
        int[] nums2 = new int[]{1, 3, 4, 2};
        System.out.println(Arrays.toString(test(nums1, nums2)));
    }
}
